package 单周赛.history;

import java.util.*;

/**
 *
 */
public class 第312场单周赛 {

    public static void main(String[] args) {

        sortPeople(new String[]{"Mary", "John", "Emma"}, new int[]{180, 165, 170});

        System.out.println(longestSubarray(new int[]{1, 2, 3, 4}));

        //输出：
        //[3,4]
        //预期：
        //[3]
        System.out.println(goodIndices(new int[]{253747, 459932, 263592, 354832, 60715, 408350, 959296}, 2));

    }

    public static String[] sortPeople(String[] names, int[] heights) {
        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < heights.length; i++) {
            map.put(heights[i], names[i]);
        }
        Arrays.sort(heights);

        for (int i = 0; i < heights.length; i++) {
            names[names.length - 1 - i] = map.get(heights[i]);
        }
        return names;
    }

    /**
     * 脑筋急转弯
     * 找出最大的数，连续最长的数组
     *
     * @param nums
     * @return
     */
    public static int longestSubarray(int[] nums) {
        int maxLen = 0, curLen = 0, maxNum = nums[0];
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
        }

        for (int num : nums) {
            if (num == maxNum) {
                curLen++;
                maxLen = Math.max(maxLen, curLen);
            } else {
                curLen = 0;
            }
        }
        return maxLen;
    }

    /**
     * 6190. 找到所有好下标 显示英文描述
     * 给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。
     * <p>
     * 对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：
     * <p>
     * 下标 i 之前 的 k 个元素是 非递增的 。
     * 下标 i 之后 的 k 个元素是 非递减的 。
     * 按 升序 返回所有好下标。
     * <p>
     * 单调栈
     *
     * @param nums
     * @param k
     * @return
     */
    public static List<Integer> goodIndices(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();

        Deque<Integer> stack = new ArrayDeque<>();
        int idx = 0;
        while (idx < nums.length) {
            if (stack.size() >= k) {
                set.add(idx);
            }
            if (!stack.isEmpty() && stack.peekFirst() < nums[idx]) {
                // 注意：单调栈里面的元素必须是连续的！！！
                stack.clear();
                System.out.println();
            }
            stack.addFirst(nums[idx]);
            idx++;
        }

        idx = nums.length - 1;
        stack.clear();
        while (idx >= 0) {
            if (stack.size() >= k && set.contains(idx)) {
                list.add(0, idx);
            }
            if (!stack.isEmpty() && stack.peekFirst() < nums[idx]) {
                stack.clear();
                System.out.println();
            }
            stack.addFirst(nums[idx]);
            idx--;
        }

        return list;
    }

}
